Display Problems

Imagination is more important than knowledge... Albert Einstein

Guess is more important than calculation --- Knowhowacademy.com

Numbers - Modular Arithmetic

For COMPETITION
Number of Total Problems: 12.
FOR PRINT ::: (Book)

Problem Num : 1

From : AMC10B

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer $S$ . For example, if $N = 749$ , Bernardo writes the numbers $10,444$ and $3,245$ , and LeRoy obtains the sum $S = 13,689$ . For how many choices of $n$ are the two rightmost digits of $S$ , in order, the same as those of $2N$ ?
$extbf{(A)} 5 qquad extbf{(B)} 10 qquad extbf{(C)} 15 qquad extbf{(D)} 20 qquad extbf{(E)} 25$

'

Category Modular Arithmetic

Analysis

Solution/Answer
First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities.
Say that $N equiv a pmod{6}$
also that $N equiv b pmod{5}$
After some inspection, it can be seen that $a=b$ , and $b < 5$ , so $N equiv a pmod{6}$ , $N equiv a pmod{5}$ , $implies N=a pmod{30}$ , $0 le a le 4$
Therefore, $N$ can be written as $30x+y$ and $2N$ can be written as $60x+2y$
Keep in mind that $y$ can be $0, 1, 2, 3, 4$ , five choices; Also, we have already found which digits of $y$ will add up into the units digits of $2N$ .
Now, examine the tens digit, $x$ by using $mod{25}$ and $mod{36}$ to find the tens digit (units digits can be disregarded because $y=0,1,2,3,4$ will always work) Then we see that $N=30x+y$ and take it $mod{25}$ and $mod{36}$ to find the last two digits in the base $5$ and $6$ representation. $N equiv 30x pmod{36}$ $N equiv 30x equiv 5x pmod{25}$ Both of those must add up to $2Nequiv60x pmod{100}$
( $33 ge x ge 4$ )
Now, since $y=0,1,2,3,4$ will always work if $x$ works, then we can treat $x$ as a units digit instead of a tens digit in the respective bases and decrease the mods so that $x$ is now the units digit. $N equiv 6x equiv x pmod{5}$ $N equiv 5x pmod{6}$ $2Nequiv 6x pmod{10}$
Say that $x=5m+n$ (m is between 0-6, n is 0-4 because of constraints on x) Then
$N equiv 5m+n pmod{5}$ $N equiv 25m+5n pmod{6}$ $2Nequiv30m + 6n pmod{10}$
and this simplifies to
$N equiv n pmod{5}$ $N equiv m+5n pmod{6}$ $2Nequiv 6n pmod{10}$
From inspection, when
$n=0, m=6$
$n=1, m=6$
$n=2, m=2$
$n=3, m=2$
$n=4, m=4$
This gives you $5$ choices for $x$ , and $5$ choices for $y$ , so the answer is $5* 5 = oxed{ extbf{(E) }25}$

Answer:

Problem Num : 2

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
In base $10$ , the number $2013$ ends in the digit $3$ . In base $9$ , on the other hand, the same number is written as $(2676)_{9}$ and ends in the digit $6$ . For how many positive integers $b$ does the base- $b$ -representation of $2013$ end in the digit $3$ ?

$extbf{(A)} 6qquad extbf{(B)} 9qquad extbf{(C)} 13qquad extbf{(D)} 16qquad extbf{(E)} 18$
'

Category Modular Arithmetic

Analysis

Solution/Answer
We want the integers $b$ such that $2013equiv 3pmod{b} Rightarrow b$ is a factor of $2010$ . Since $2010=2 cdot 3 cdot 5 cdot 67$ , it has $(1+1)(1+1)(1+1)(1+1)=16$ factors. Since $b$ cannot equal $1, 2,$ or $3$ , as these cannot have the digit 3 in their base representations, our answer is $16-3=oxed{ extbf{(C) }13}$

Answer:

Problem Num : 3

From : AMC10B

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
Mrs. Walter gave an exam in a mathematics class of five students. She entered the scores in random order into a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) were 71,76,80,82, and 91. What was the last score Mrs. Walters entered?
$ext{(A)} 71 qquad ext{(B)} 76 qquad ext{(C)} 80 qquad ext{(D)} 82 qquad ext{(E)} 91$
'

Category Modular Arithmetic

Analysis

Solution/Answer
Solution 1

The first number is divisible by 1.
The sum of the first two numbers is even.
The sum of the first three numbers is divisible by 3.
The sum of the first four numbers is divisible by 4.
The sum of the first five numbers is 400.
Since 400 is divisible by 4, the last score must also be divisible by 4. Therefore, the last score is either 76 or 80.
Case 1: 76 is the last number entered.
Since $400equiv 76equiv 1pmod{3}$ , the fourth number must be divisible by 3, but none of the scores are divisible by 3.
Case 2: 80 is the last number entered.
Since $80equiv 2pmod{3}$ , the fourth number must be $2pmod{3}$ . That number is 71 and only 71. The next number must be 91, since the sum of the first two numbers is even. So the only arrangement of the scores $76, 82, 91, 71, 80$ $Rightarrow ext{(C)}$

Solution 2

We know the first sum of the first three numbers must be divisible by 3, so we write out all 5 numbers $pmod{3}$ , which gives 2,1,2,1,1, respectively. Clearly the only way to get a number divisible by 3 by adding three of these is by adding the three ones. So those must go first. Now we have an odd sum, and since the next average must be divisible by 4, 71 must be next. That leaves 80 for last, so the answer is $mathrm{C}$ .

Answer:

Problem Num : 4

From : AMC10B

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
How many distinct four-digit numbers are divisible by $3$ and have $23$ as their last two digits?
$extbf{(A) }27qquad extbf{(B) }30qquad extbf{(C) }33qquad extbf{(D) }81qquad extbf{(E) }90$
'

Category Modular Arithmetic

Analysis

Solution/Answer
Solution 1

To test if a number is divisible by three, you add up the digits of the number. If the sum is divisible by three, then the original number is a multiple of three. If the sum is too large, you can repeat the process until you can tell whether it is a multiple of three. This is the basis for the solution. Since the last two digits are $23$ , the sum of the digits is $2+3 = 5$ (therefore it is not divisible by three). However certain numbers can be added to make the sum of the digits a multiple of three.
$5+1 = 6$ ,
$5+4 = 9$ , and so on.
However since the largest four-digit number ending with $23$ is $9923$ , the maximum sum is
$5+18 = 23$ .
Using that process we can fairly quickly compile a list of the sum of the first two digits of the number.
${1, 4, 7, 10, 13, 16}$
Now we find all the two-digit numbers that have any of the sums shown above. We can do this by listing all the two digit numbers $xy$ in separate cases.
$I. x+y = 1, {10} = 1$ $II. x+y = 4, {13, 22, 31, 40} = 4$ $III. x+y = 7, {16, 25, 34, 43, 52, 61, 70} = 7$ $IV. x+y = 10, {19, 28, 37, 46, 55, 64, 73, 82, 91} = 9$ $V. x+y = 13, {49, 58, 67, 76, 85, 94} = 6$ $VI. x+y = 16, {79, 88, 97} = 3$
And finally, we add the number of elements in each set.
$1+4+7+9+6+3 = oxed{ extbf{(B)} 30}$

Solution 2

A number divisible by $3$ has all its digits add to a multiple of $3.$ The last two digits are $2$ and $3$ and add up to $5 equiv 2 ( ext{mod} 3).$ Therefore the first two digits must add up to $1 ( ext{mod} 3).$ $4$ digits (including $0$ ) are $0 ( ext{mod} 3),$ $3$ are $1 ( ext{mod} 3),$ and $3$ are $2 ( ext{mod} 3).$ The following combinations are equivalent to $1 ( ext{mod} 3)$ :
$0 ( ext{mod} 3)+1 ( ext{mod} 3) equiv 1 ( ext{mod} 3)+0 ( ext{mod} 3) equiv 2 ( ext{mod} 3) +2 ( ext{mod}...$
Let the first term in each combination represent the thousands digit and the second term represent the hundreds digit. We can use this to find the total amount of four-digit numbers.
$3cdot3 + 3cdot4 + 3cdot3 = 9 + 12 + 9 = oxed{ extbf{(B)} 30}$

Answer:

Problem Num : 5

From : AMC10B

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
The first term of a sequence is $2005$ . Each succeeding term is the sum of the cubes of the digits of the previous terms. What is the $2005^ ext{th}$ term of the sequence?
$mathrm{(A)} {{{29}}} qquad mathrm{(B)} {{{55}}} qquad mathrm{(C)} {{{85}}} qquad mathrm{(D)} {{{133}}} qquad mat...$
'

Category Modular Arithmetic

Analysis

Solution/Answer
Performing this operation several times yields the results of $133$ for the second term, $55$ for the third term, and $250$ for the fourth term. The sum of the cubes of the digits of $250$ equal $133$ , a complete cycle. The cycle is... excluding the first term, the $2^{ ext{nd}}$ , $3^{ ext{rd}}$ , and $4^{ ext{th}}$ terms will equal $133$ , $55$ , and $250$ , following the fourth term. Any term number that is equivalent to $1 ( ext{mod} 3)$ will produce a result of $250$ . It just so happens that $2005equiv 1 ( ext{mod} 3)$ , which leads us to the answer of $oxed{mathrm{(E)} 250}$ .

Answer:

Problem Num : 6

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
What is the units digit of $13^{2003}$ ?
$mathrm{(A) } 1qquad mathrm{(B) } 3qquad mathrm{(C) } 7qquad mathrm{(D) } 8qquad mathrm{(E) } 9$
'

Category Modular Arithmetic

Analysis

Solution/Answer
$13^{2003}equiv 3^{2003}pmod{10}$
Since $3^4=81equiv1pmod{10}$ :
$3^{2003}=(3^{4})^{500}cdot3^{3}equiv1^{500}cdot27equiv7pmod{10}$
Therefore, the units digit is $7 Rightarrow C$

Answer:

Problem Num : 7

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
Let $n$ be a $5$ -digit number, and let $q$ and $r$ be the quotient and the remainder, respectively, when $n$ is divided by $100$ . For how many values of $n$ is $q+r$ divisible by $11$ ?
$mathrm{(A) } 8180qquad mathrm{(B) } 8181qquad mathrm{(C) } 8182qquad mathrm{(D) } 9000qquad mathrm{(E) } 9...$
'

Category Modular Arithmetic

Analysis

Solution/Answer
Solution 1

When a $5$ -digit number is divided by $100$ , the first $3$ digits become the quotient, $q$ , and the last $2$ digits become the remainder, $r$ .
Therefore, $q$ can be any integer from $100$ to $999$ inclusive, and $r$ can be any integer from $0$ to $99$ inclusive.
For each of the $9cdot10cdot10=900$ possible values of $q$ , there are at least $leftlfloor frac{100}{11} ight floor = 9$ possible values of $r$ such that $q+r equiv 0pmod{11}$ .
Since there is $1$ "extra" possible value of $r$ that is congruent to $0pmod{11}$ , each of the $leftlfloor frac{900}{11} ight floor = 81$ values of $q$ that are congruent to $0pmod{11}$ have $1$ more possible value of $r$ such that $q+r equiv 0pmod{11}$ .
Therefore, the number of possible values of $n$ such that $q+r equiv 0pmod{11}$ is $900cdot9+81cdot1=8181 Rightarrow B$ .

Solution 2

Let $n$ equal $overline{abcde}$ , where $a$ through $e$ are digits. Therefore,
$q=overline{abc}=100a+10b+c$
$r=overline{de}=10d+e$
We now take $q+rmod{11}$ :
$q+r=100a+10b+c+10d+eequiv a-b+c-d+eequiv 0mod{11}$
The divisor trick for 11 is as follows:
"Let $n=overline{a_1a_2a_3cdots a_x}$ be an $x$ digit integer. If $a_1-a_2+a_3-cdots +(-1)^{x-1} a_x$ is divisible by $11$ , then $n$ is also divisible by $11$ ."
Therefore, the five digit number $n$ is divisible by 11. The 5-digit multiples of 11 range from $910cdot 11$ to $9090cdot 11$ . There are $8181Rightarrow mathrm{(B)}$ divisors of 11 between those inclusive.

Solution 3

Since $q$ is a quotient and $r$ is a remainder when $n$ is divided by $100$ . So we have $n=100q+r$ . Since we are counting choices where $q+r$ is divisible by $11$ , we have $n=99q+q+r=99q+11k$ for some $k$ . This means that $n$ is the sum of two multiples of $11$ and would thus itself be a divisor of $11$ . Then we can count all the four digit divisors of $11$ as in Solution 2. (This solution is essentially the same as Solution 2, but it does not necessarily involve mods and so could potentially be faster.)

Notes

The part labeled "divisor trick" actually follows from the same observation we made in the previous step: $10equiv (-1)pmod{11}$ , therefore $10^{2k}equiv 1$ and $10^{2k+1}equiv (-1)$ for all $k$ . For a $5-$ digit number $overline{abcde}$ we get $overline{abcde}equiv acdot 1 + bcdot(-1) + ccdot 1 + dcdot(-1) + ecdot 1 = a-b+c-d+e$ , as claimed.
Also note that in the "divisor trick" we actually want to assign the signs backwards - if we make sure that the last sign is a $+$ , the result will have the same remainder modulo $11$ as the original number.

Answer:

Problem Num : 8

From : AMC10B

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
What is the remainder when $3^0 + 3^1 + 3^2 + cdots + 3^{2009}$ is divided by 8?
$mathrm{(A)} 0qquadmathrm{(B)} 1qquadmathrm{(C)} 2qquadmathrm{(D)} 4qquadmathrm{(E)} 6$
'

Category Modular Arithmetic

Analysis

Solution/Answer
Solution 1

The sum of any four consecutive powers of 3 is divisible by $3^0 + 3^1 + 3^2 +3^3 = 40$ and hence is divisible by 8. Therefore

$(3^2 + 3^3 + 3^4 + 3^5) + cdots + (3^{2006} + 3^{2007} + 3^{2008} + 3^{2009})$

is divisible by 8. So the required remainder is $3^0 + 3^1 = oxed {4}$ . The answer is $mathrm{(D)}$ .

Solution 2

We have $3^2 = 9 equiv 1 pmod 8$ . Hence for any $k$ we have $3^{2k}equiv 1^k = 1 pmod 8$ , and then $3^{2k+1} = 3cdot 3^{2k} equiv 3cdot 1 = 3 pmod 8$ .
Therefore our sum gives the same remainder modulo $8$ as $1 + 3 + 1 + 3 + 1 + cdots + 1 + 3$ . There are $2010$ terms in the sum, hence there are $2010/2 = 1005$ pairs $1+3$ , and thus the sum is $1005 cdot 4 = 4020 equiv 20 equiv oxed{4} pmod 8$ .

Answer:

Problem Num : 9

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
Let $k={2008}^{2}+{2}^{2008}$ . What is the units digit of $k^2+2^k$ ?
$mathrm{(A)} 0qquadmathrm{(B)} 2qquadmathrm{(C)} 4qquadmathrm{(D)} 6qquadmathrm{(E)} 8$
'

Category Modular Arithmetic

Analysis

Solution/Answer
$k equiv 2008^2 + 2^{2008} equiv 8^2 + 2^4 equiv 4+6 equiv 0 pmod{10}$ .
So, $k^2 equiv 0 pmod{10}$ . Since $k = 2008^2+2^{2008}$ is a multiple of four and the units digit of powers of two repeat in cycles of four, $2^k equiv 2^4 equiv 6 pmod{10}$ .
Therefore, $k^2+2^k equiv 0+6 equiv 6 pmod{10}$ . So the units digit is $6 Rightarrow D$ .

Answer:

Problem Num : 10

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

'
For $k > 0$ , let $I_k = 10ldots 064$ , where there are $k$ zeros between the $1$ and the $6$ . Let $N(k)$ be the number of factors of $2$ in the prime factorization of $I_k$ . What is the maximum value of $N(k)$ ?
$extbf{(A)} 6qquad extbf{(B)} 7qquad extbf{(C)} 8qquad extbf{(D)} 9qquad extbf{(E)} 10$
'

Category Modular Arithmetic

Analysis

Solution/Answer
The number $I_k$ can be written as $10^{k+2} + 64 = 5^{k+2}cdot 2^{k+2} + 2^6$ .
For $kin{1,2,3}$ we have $I_k = 2^{k+2} left( 5^{k+2} + 2^{4-k} ight)$ . The first value in the parentheses is odd, the second one is even, hence their sum is odd and we have $N(k)=k+2leq 5$ .
For $kgeq 5$ we have $I_k=2^6 left( 5^{k+2}cdot 2^{k-4} + 1 ight)$ . For $k>4$ the value in the parentheses is odd, hence $N(k)=6$ .
This leaves the case $k=4$ . We have $I_4 = 2^6 left( 5^6 + 1 ight)$ . The value $5^6 + 1$ is obviously even. And as $5equiv 1 pmod 4$ , we have $5^6 equiv 1 pmod 4$ , and therefore $5^6 + 1 equiv 2 pmod 4$ . Hence the largest power of $2$ that divides $5^6+1$ is $2^1$ , and this gives us the desired maximum of the function $N$ : $N(4) = oxed{7}$ .

Alternate Solution

Notice that 2 is a prime factor of an integer $n$ if and only if $n$ is even. Therefore, given any sufficiently high positive integral value of $k$ , dividing $I_k$ by $2^6$ yields a terminal digit of zero, and dividing by 2 again leaves us with $2^7 * a = I_k$ where $a$ is an odd integer. Observe then that $oxed{7}$ must be the maximum value for $N(k)$ because whatever value we choose for $k$ , $N(k)$ must be less than or equal to 7.

Answer:

Array ( [0] => 8207 [1] => 7957 [2] => 8219 [3] => 8004 [4] => 8035 [5] => 7782 [6] => 7787 [7] => 8122 [8] => 7880 [9] => 7909 ) 121 2